Digital data transmissions over wired and wireless channels may be corrupted, for instance, by noise in the channel, by interference from other transmissions, or by other environmental factors. Even with clear communication channels, which lend themselves to high data rates, it may not be possible to appropriately decode the data stream with the requisite error rates. In order to solve this problem, many communication systems employ error-correction techniques to aid in communication.
One technique utilized for error correction is the Low-density parity-check (LDPC) codes, which is used to provide powerful protection of the information vector to be transmitted.
An LDPC code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over GF(q), q≧2. If q=2, the code is binary. As with all linear block codes, a k-bit information vector s1×k is generally encoded by the code generator matrix Gk×n to become an n-bit codeword x1×n, and the code rate is r=k/n. The codeword x is sent by the transmitter through a noisy channel, and at the receiver the received signal vector y is passed to the decoder to estimate the information vector s1×k.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix Hm×n span the m-dimensional dual space C⊥, where m=n−k. Since x=sG and GHT=0, it follows that xHT=0 for all codewords in subspace C, where “T” denotes matrix transpose. In the discussion of LDPC codes, this is generally written asHxT=0T,  (1)where 0 is a row vector of all zeros, and the codeword x=[s p]=[s0, s1, . . . ,sk−1, p0, p1, . . . , pm−1], where p0, . . . pm−1 are the parity-check bits; and s0, . . . sk−1 are the systematic bits, equal to the information bits, or data within the information vector.
For an LDPC code, the density of H is low, i.e., there are only a small percentage of 1's in H, allowing good error-correcting performance and simple decoding when compared to a high-density H. An H matrix can be also described by a bipartite graph. Each 1 in H defines an edge (i.e., a connection between a variable node and a check node) in the bipartite graph, each column in H corresponds to a variable node in the bipartite graph, and each row in H corresponds to a check node in the bipartite graph.
An example of H matrix is shown below to illustrate the relationship between the parity-check matrix, the parity-check equations, and the bipartite graph. Let an n=12, rate-½ code be defined by
                              H          =                                                    [                            ⁢                              H                s                            ⁢                                                                H                  p                                ]                                      =                                                                                [                                                                                            1                                                                          0                                                                          1                                                                          0                                                                          0                                                                          0                                                                          1                                                                          1                                                                          0                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                          1                                                                          0                                                                          0                                                                          1                                                                          1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                          0                                                                          1                                                                          1                                                                          0                                                                          1                                                                          1                                                                          0                                                                          0                                                                                                                      1                                                                          0                                                                          0                                                                          1                                                                          0                                                                          0                                                                          0                                                                          0                                                                          0                                                                          1                                                                          1                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                          1                                                                          0                                                                          0                                                                          0                                                                          0                                                                          0                                                                          1                                                                          1                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                          0                                                                          1                                                                          1                                                                          0                                                                          0                                                                          0                                                                          0                                                                          1                                                                                      ]                                    }                                                  ︸                  n                                            ⁢              m                                      ,                            (        2        )            with the left side portion corresponding to k (=6) information bits s, the right side portion corresponding to m (=6) parity-check bits p. Applying (1), the H in (2) defines six parity-check equations as follows:
                    {                                                                            ⁢                                                                            x                      0                                        +                                          x                      2                                        +                                          x                      6                                        +                                          x                      7                                                        =                  0                                                                                                                        ⁢                                                                            x                      1                                        +                                          x                      4                                        +                                          x                      7                                        +                                          x                      8                                                        =                  0                                                                                                                        ⁢                                                                            x                      2                                        +                                          x                      5                                        +                                          x                      6                                        +                                          x                      8                                        +                                          x                      9                                                        =                  0                                                                                                                        ⁢                                                                            x                      0                                        +                                          x                      3                                        +                                          x                      9                                        +                                          x                      10                                                        =                  0                                                                                                                        ⁢                                                                            x                      1                                        +                                          x                      4                                        +                                          x                      10                                        +                                          x                      11                                                        =                  0                                                                                                                        ⁢                                                                            x                      3                                        +                                          x                      5                                        +                                          x                      6                                        +                                          x                      11                                                        =                  0                                                                                        (        3        )            H can also be described by the bipartite graph shown in FIG. 1.
An LDPC decoder can contain a very high level of parallelism. To help keep routing and memory management issues in check, many LDPC codes are “architecture-aware” or “structured” to facilitate efficient LDPC decoding via iterative message passing algorithms such as the standard belief propagation (SBP) or layered belief propagation (LBP). Structured LDPC codes possessing a partial dual-diagonal structure have been adopted in standards such as IEEE 802.16e and IEEE draft 802.11n.
Turbo decoding of an LDPC code may be desired. However, it is not clear how to turbo decode LDPC codes that contain a partial dual diagonal parity-check portion. In addition, it is not clear how to build a turbo decoder for a structured LDPC code decoder that avoids contentions in memory access. In a high throughput decoder several processors operate in parallel, leading to multiple read/write requests from several memory banks. In such decoders, memory access contentions (or memory access conflicts or collisions) occur when more than one message is to be written to or read from the same memory bank at the same time. Extra hardware or excessive storage is required to resolve these conflicts. Therefore, a method and apparatus for turbo like encoding and decoding algorithm is needed to handle LDPC codes with a partial dual diagonal structure, and a turbo like decoding (TLD) algorithm is needed where a contention-free interleaver is used to enable parallel memory accesses.